package simple.string;

/**
 * <a href="https://leetcode.cn/problems/greatest-common-divisor-of-strings/">1071. 字符串的最大公因子</a>
 * 对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
 * 给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。
 * 示例 1：
 *   输入：str1 = "ABCABC", str2 = "ABC"
 *   输出："ABC"
 * 示例 2：
 *   输入：str1 = "ABABAB", str2 = "ABAB"
 *   输出："AB"
 * 示例 3：
 *   输入：str1 = "LEET", str2 = "CODE"
 *   输出：""
 * 提示：
 *   1 <= str1.length, str2.length <= 1000
 *   str1 和 str2 由大写英文字母组成
 * @author 刘学松
 * @date 2023-07-07 15:45
 */
public class 字符串的最大公因子 {
    public String gcdOfStrings(String str1, String str2) {
        if (!str1.concat(str2).equals(str2.concat(str1))) {
            return "";
        }
        return str1.substring(0, gcd(str1.length(), str2.length()));
    }

    public int gcd(int len1, int len2) {
        int n = len1 % len2;
        while (n != 0) {
            len1 = len2;
            len2 = n;
            n = len1 % len2;
        }
        return len2;
    }
}
